<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>Rotated Digits</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="rotated-digits">Rotated Digits</h1>
<ol start="788">
<li>Rotated Digits</li>
</ol>
<ul>
<li><a href="https://leetcode.com/problems/rotated-digits/">https://leetcode.com/problems/rotated-digits/</a></li>
</ul>
<p>X is a good number if after rotating each digit individually by 180 degrees, we get a valid number that is different from X.  Each digit must be rotated - we cannot choose to leave it alone.</p>
<p>A number is valid if each digit remains a digit after rotation. 0, 1, and 8 rotate to themselves; 2 and 5 rotate to each other (on this case they are rotated in a different direction, in other words 2 or 5 gets mirrored); 6 and 9 rotate to each other, and the rest of the numbers do not rotate to any other number and become invalid.</p>
<pre><code><code><div>Now given a positive number N, how many numbers X from 1 to N are good?

Example:
Input: 10
Output: 4
Explanation: 
There are four good numbers in the range [1, 10] : 2, 5, 6, 9.
Note that 1 and 10 are not good numbers, since they remain unchanged after rotating.
Note:
</div></code></code></pre>
<p>N  will be in range [1, 10000].</p>
<h1 id="1-暴力解法">1. 暴力解法</h1>
<ul>
<li><a href="https://leetcode.com/problems/rotated-digits/discuss/116530/O(logN)-Time-O(1)-Space">https://leetcode.com/problems/rotated-digits/discuss/116530/O(logN)-Time-O(1)-Space</a></li>
</ul>
<p>5 lines, self-explaining:</p>
<pre><code class="language-python"><div><span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">rotatedDigits</span><span class="hljs-params">(self, N)</span>:</span>
        s1 = set([<span class="hljs-number">1</span>, <span class="hljs-number">8</span>, <span class="hljs-number">0</span>])
        s2 = set([<span class="hljs-number">1</span>, <span class="hljs-number">8</span>, <span class="hljs-number">0</span>, <span class="hljs-number">6</span>, <span class="hljs-number">9</span>, <span class="hljs-number">2</span>, <span class="hljs-number">5</span>])
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">isGood</span><span class="hljs-params">(x)</span>:</span>
            s = set([int(i) <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> str(x)])
            <span class="hljs-keyword">return</span> s.issubset(s2) <span class="hljs-keyword">and</span> <span class="hljs-keyword">not</span> s.issubset(s1)
        <span class="hljs-keyword">return</span> sum(isGood(i) <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(N + <span class="hljs-number">1</span>))
</div></code></pre>
<p>O(NlogN) solution is simple in all languages.</p>
<p>同样的思路，我写的就和繁琐</p>
<pre><code class="language-python"><div>
</div></code></pre>
<h1 id="2-olgn-解法">2. O(lgN) 解法</h1>
<p>Here is solution in O(logN) complexity.</p>
<p>Consider the number 642. We can break this apart into the three distinct regions [0,600), [600,640), [640,642). The</p>
<p>less significant digits 4 and 2 will have no effect on the amount of good numbers in the [0,600) region.</p>
<pre><code class="language-python"><div><span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">rotatedDigits</span><span class="hljs-params">(self, N)</span>:</span>
        s1 = set([<span class="hljs-number">0</span>, <span class="hljs-number">1</span>, <span class="hljs-number">8</span>])
        s2 = set([<span class="hljs-number">0</span>, <span class="hljs-number">1</span>, <span class="hljs-number">8</span>, <span class="hljs-number">2</span>, <span class="hljs-number">5</span>, <span class="hljs-number">6</span>, <span class="hljs-number">9</span>])
        s = set()
        res = <span class="hljs-number">0</span>
        N = list(map(int, str(N)))
        <span class="hljs-keyword">for</span> i, v <span class="hljs-keyword">in</span> enumerate(N):
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(v):
                <span class="hljs-keyword">if</span> s.issubset(s2) <span class="hljs-keyword">and</span> j <span class="hljs-keyword">in</span> s2:
                    res += <span class="hljs-number">7</span>**(len(N) - i - <span class="hljs-number">1</span>)
                <span class="hljs-keyword">if</span> s.issubset(s1) <span class="hljs-keyword">and</span> j <span class="hljs-keyword">in</span> s1:
                    res -= <span class="hljs-number">3</span>**(len(N) - i - <span class="hljs-number">1</span>)
            <span class="hljs-keyword">if</span> v <span class="hljs-keyword">not</span> <span class="hljs-keyword">in</span> s2:
                <span class="hljs-keyword">return</span> res
            s.add(v)
        <span class="hljs-keyword">return</span> res + (s.issubset(s2) <span class="hljs-keyword">and</span> <span class="hljs-keyword">not</span> s.issubset(s1))
</div></code></pre>
<p>详情可以参考 <a href="http://www.frankmadrid.com/ALudicFallacy/2018/02/28/rotated-digits-leet-code-788/">http://www.frankmadrid.com/ALudicFallacy/2018/02/28/rotated-digits-leet-code-788/</a></p>
<h1 id="3-dp解法-on">3. dp解法. O(N)</h1>
<ul>
<li><a href="https://leetcode.com/problems/rotated-digits/discuss/117975/Java-dp-solution-9ms">https://leetcode.com/problems/rotated-digits/discuss/117975/Java-dp-solution-9ms</a></li>
</ul>
<p>Using a int[] for dp.</p>
<ul>
<li>dp[i] = 0, invalid number</li>
<li>dp[i] = 1, valid and same number</li>
<li>dp[i] = 2, valid and different number</li>
</ul>
<pre><code class="language-java"><div>    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">rotatedDigits</span><span class="hljs-params">(<span class="hljs-keyword">int</span> N)</span> </span>{
        <span class="hljs-keyword">int</span>[] dp = <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[N + <span class="hljs-number">1</span>];
        <span class="hljs-keyword">int</span> count = <span class="hljs-number">0</span>;
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt;= N; i++){
            <span class="hljs-keyword">if</span>(i &lt; <span class="hljs-number">10</span>){
                <span class="hljs-keyword">if</span>(i == <span class="hljs-number">0</span> || i == <span class="hljs-number">1</span> || i == <span class="hljs-number">8</span>) dp[i] = <span class="hljs-number">1</span>;
                <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(i == <span class="hljs-number">2</span> || i == <span class="hljs-number">5</span> || i == <span class="hljs-number">6</span> || i == <span class="hljs-number">9</span>){
                    dp[i] = <span class="hljs-number">2</span>;
                    count++;
                }
            } <span class="hljs-keyword">else</span> {
                <span class="hljs-keyword">int</span> a = dp[i / <span class="hljs-number">10</span>], b = dp[i % <span class="hljs-number">10</span>];
                <span class="hljs-keyword">if</span>(a == <span class="hljs-number">1</span> &amp;&amp; b == <span class="hljs-number">1</span>) dp[i] = <span class="hljs-number">1</span>;
                <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(a &gt;= <span class="hljs-number">1</span> &amp;&amp; b &gt;= <span class="hljs-number">1</span>){
                    dp[i] = <span class="hljs-number">2</span>;
                    count++;
                }
            }
        }
        <span class="hljs-keyword">return</span> count;
    }
</div></code></pre>

    </body>
    </html>